1. Field of the Invention
This invention relates generally to data transmission. More particularly, the invention relates to a reduced complexity precoder method and apparatus for multicarrier systems. The precoder compensates for effects of intersymbol interference in multicarrier systems such as those employing DMT (discrete multitone modulation.)
2. Description of the Related Art
Theoretically, on a channel with a high signal-to-noise ratio, the channel capacity may be approached using a combination of channel coding in a transmitter and an ideal zero-forcing DFE (decision feedback equalizer) in a receiver. In actual systems, an ideal DFE cannot be achieved, and thus performance is lost due to effects of error propagation which occur in the DFE located in the receiver. One approach to achieving the performance of an ideal DFE is to feed back error-free decisions in a transmitter-based precoder structure. One such precoder structure is the so-called THP (Tomlinson-Harashima precoder).
A THP structure has recently been introduced for use in multicarrier systems, and in particular DMT (discrete multitone) systems. In general, any THP for DMT will be referred to hereinafter as a DMT-THP. One DMT-THP structure is described in K.W. Cheong and J.M. Cioffi, “Precoder for DMT with insufficient cyclic prefix,” International Conference on Communications, pp. 339-343, 1998. This reference is referred to herein as the “Cheong reference.” The DMT-THP disclosed therein has many desirable properties and is designed for use with DMT systems as defined by the ANSI T1.413-95 standard for ADSL (asymmetric digital subscriber lines) and related multicarrier methods (e.g., VDSL). The DMT-THP described in the Cheong reference is able to compensate for the fact that a fixed length cyclic prefix is used in the ANSI T1.413 standard. Both the Cheong reference and the ANSI standard T1.413-1995 are hereby incorporated herein by reference to provide background information useful in understanding the context of the present invention. A more traditional approach to ISI compensation is to use a TEQ (time domain equalizer) in conjunction with an FEQ (frequency domain equalizer) as is taught in U.S. Pat. No. 5,285,474. When a DMT-THP is used, no TEQ is needed.
The DMT-THP is shown by simulation in the Cheong reference to not increase the transmitted power considerably, which is a concern with THP related approaches. Moreover, the Cheong reference demonstrates the ability of the DMT-THP to compensate for the effects of intra-block and inter-block distortions inherent in passing a vector (block) sequence through a band-limited ISI (intersymbol interference) channel. The specific computational structure of the DMT-THP disclosed in the Cheong reference has one serious drawback, however. The Cheong reference teaches a structure as shown in FIG. 1 involving two unstructured complex matrix-multiplies, one with a feed-forward matrix, W and another with a feedback matrix, B. These matrices are “unstructured complex” because in general none of the elements therein are guaranteed to be zero, and these generally nonzero elements are defined over the complex field of numbers. Multiplication of a length-N complex vector by an unstructured N×N complex matrix requires O(N2) complex operations. Because DMT systems use a vector of length N=512, and the entire DMT transmitter minus the precoder requires O(N log2 (N)), the DMT-THP of the Cheong reference increases the cost of the DMT transmitter by a factor of roughly
            2      ⁢      N                      log        2            ⁢      N        =            1024      9        ≅    114.  The factor of two in the numerator is due to the presence of two unstructured matrix multiplications in the DMT-THP. As DMT systems already require very powerful DSPs to implement, the prior art DMT-THP structure appears to be out of reach of current technology. Even when processor speeds increase, host based implementations would be desired, so the need for a reduced complexity structure will remain.
In the Cheong reference it is stated (page 341): “Note also that because of the matrix multiplies, we have O(N2) complexity for the precoder. Since H1 and H2 are usually sparse matrices, the complexity can be reduced. Also, we could introduce approximate solutions for W and B so that we can implement them with less complexity, although this would introduce distortion at the channel output.” The Cheong reference teaches one to exploit the “usually” sparse structure of H1 and H2 to reduce the O(N2) complexity. If this approach is taken, then channels with long tails will not be able to be accommodated. Hence this form of complexity reduction cannot be used in production systems without limiting worst-case performance because the amount of computations required depends on a given channel's tail length. To compensate for this effect, a “worst case” design must be used, and this substantially negates the complexity reduction. If the second approach is followed, a trade-off involving an inexact solution which introduces distortion must be accepted. No such approximation methods are specifically taught, and if obvious approximations are used, such as assuming the channel to appear to be circulant for all practical purposes, unspecified amounts of distortion will be introduced. This added distortion will degrade system performance by reducing the noise margin.
The foregoing indicates a recognized but unmet need for a reduced complexity DMT-THP. It would be desirable to have a DMT-THP structure that could produce the same output as the prior art DMT-THP, but with a fraction of the cost, for example with a savings of an order of magnitude (10×). It would also be desirable to provide a precoder structure and method which could perform ISI compensation without the need for a cyclic prefix. It would be desirable to introduce some general matrix computation methods and structures which could be used in related forms of transform domain precoders. Moreover, it would be desirable to have a matrix processing structure within a DMT-THP which revealed new structures and methods to form fairly accurate approximate solutions for further savings.